1. Field of the Invention
The invention relates generally to communication systems and, more particularly, to multiple access protocols for use over a shared communications medium.
2. Discussion of Related Art
In today's information age, there is an increasing need for high speed communications that provides guaranteed quality of service (QoS) for an ever-increasing number of communications consumers. To that end, communications networks and technologies are evolving to meet current and future demands. Specifically, new networks are being deployed which reach a larger number of end users, and protocols are being developed to utilize the added bandwidth of these networks efficiently.
One technology that will be employed increasingly in the future is the shared-medium network. A shared medium network is one in which a single communications channel (the shared channel) is shared by a number of end users such that uncoordinated transmissions from different end users may interfere with each other. In modern broadband communications networks, the shared communications channel is typically one of a number of frequency bands carried over a shared physical medium, such as a hybrid fiber-optic/coaxial cable (HFC) network or by electromagnetic waves in free space. Since communications networks typically have a limited number of communications channels, the shared medium network allows many end users to gain access to the network over a single communications channel, thereby allowing the remaining communications channels to be used for other purposes. However, the shared medium network is only feasible when each end user only transmits data intermittently, allowing other end users to transmit during periods of silence.
In the shared medium network, each end user interfaces to the shared channel by means of an Access Interface Unit (AIU) which allows the end user to transmit and receive information via the shared channel. A single AIU may support one or a number of end users. Each end user wishing to utilize the shared channel participates in a Medium Access Control (MAC) protocol which provides a set of rules and procedures for accessing the shared channel. For convenience, each participant in the MAC protocol is referred to as a MAC User.
FIG. 1 is a logical representation of a shared medium network 100 as is known in the art. As illustrated in FIG. 1, a headend unit 110 is coupled to a plurality of AIUs 120.sub.a through 120.sub.n (collectively referred to as AIUs 120) via a shared channel 130. In the preferred embodiment, the shared channel 130 is one of a number of communications channels carried by a shared physical medium such as an HFC or wireless network. In other embodiments, the shared physical medium may be coaxial cable, fiber-optic cable, twisted pair wires, and so on, and may also include air, atmosphere, or space for wireless and satellite communication. The headend unit 110 is also coupled to a communications network 140, which may include networks such as the Internet, on-line services, telephone and cable networks, and other communication systems.
Continuing to refer to FIG. 1, in the preferred embodiment, the shared physical medium, such as an HFC or wireless network, has or supports a plurality of communications channels. For ease of reference, the communications channels in which a headend unit, such as the headend unit 110, transmits information, signals, or other data to an AIU, such as AIU 120.sub.n, are referred to as downstream channels. Also for ease of reference, the communications channels in which an AIU, such as AIU 120.sub.n, transmits information, signals, or other data to a headend unit, such as headend unit 110, are referred to as upstream channels. These various upstream and downstream channels may, of course, be the same physical channel or may be separate physical channels, for example, through time-division multiplexing or frequency-division multiplexing. These various channels may also be logically divided in other ways, in addition to upstream and downstream directions. In the preferred embodiment, the communications medium is an HFC network, with downstream channels in the frequency spectrum (band) typically 50-750 MHz (and up to 1 GHz), and with upstream channels in the frequency spectrum typically 5-42 MHz.
In a simple model of an exemplary HFC network, the headend unit uses a single downstream channel to send information, including poll messages, to the MAC Users, and a single upstream channel is used by the MAC Users to send information to the headend unit. Since the headend unit is the only device which transmits on the downstream channel, the downstream channel is not a "shared channel" as that term is applied to the present invention. However, since multiple MAC Users transmit on the upstream channel, the upstream channel is a shared channel, and the MAC protocol must provide for orderly access to the channel so as to maximize the data throughput over the channel.
A number of different MAC protocols have been developed for use over a shared channel. These protocols can generally be categorized as contention-free protocols, which avoid collisions on the shared channel by means of various scheduling methods, and contention-based protocols, which do not avoid collisions but instead resolve any collisions that do occur on the shared channel. Contention-free protocols, such as time-division multiple access (TDMA) and round-robin polling protocols, are typically less efficient than contention-based protocols under light loads because the contention-free protocols generally allocate some amount of bandwidth to each MAC User whether or not the MAC User has information to send. On the other hand, contention-based protocols only allocate bandwidth to those MAC Users that have information to send, although some amount of bandwidth is wasted whenever collision resolution is required. Thus, the effectiveness of a MAC protocol is generally dependent on the number of MAC Users.
There are many variations of each protocol category. One contention-based MAC protocol uses a single headend unit, situated at a common receiving end of the shared channel and able to transmit messages to all MAC Users sharing the channel, to coordinate access to the shared channel. A hybrid contention/polling technique is used wherein "active" MAC Users are given contention-free access to the channel by individually addressed (select) poll messages, while "inactive" MAC Users are provided opportunities to contend for access to the channel.
In the hybrid contention/polling protocol, the headend unit characterizes each MAC User as either "active" or "inactive" based on the MAC User's responses to poll messages. The headend unit maintains a list of the "active" MAC Users (referred to as the "select poll list") and a list of the "inactive" MAC Users (referred to as the "contention poll list"). In practice, the select poll list may be an aggregate of a number of lists (e.g., an exemplary embodiment splits the select poll list into separate fast poll and medium poll lists which are used to determine the frequency at which the headend unit polls the MAC Users on those lists). The MAC Users on the select poll list are polled individually while the MAC Users on the contention poll list are routinely polled in groups and must contend for access to the shared channel. For convenience, an individually addressed poll message is referred to as a select poll (SPoll) while a group addressed poll message is referred to as a limited contention poll (LCPoll).
The SPoll is individually addressed to a particular MAC User and is intended only for that MAC User. The individually addressed MAC User must respond to the SPoll, while all other MAC Users must ignore the SPoll. The individually addressed MAC User responds to the SPoll by transmitting either a data message, if the MAC User has data to transmit, or a Negative Acknowledgment (NAK), if the MAC User has no data to transmit.
Upon being individually polled by the headend unit, MAC Users on the select poll list that remain "active" (i.e., by transmitting a data message in response to a SPoll within a predetermined interval) are left on the select poll list. However, MAC Users on the select poll list that become "inactive" (i.e., by responding with a NAK to each SPoll received during a predetermined interval) are moved onto the contention poll list and are instructed (either explicitly or implicitly) by the headend unit to respond to LCPolls.
The LCPoll is addressed to a group of MAC Users by specifying in the LCPoll a range of MAC User addresses and a service group identifier. Only MAC Users in the specified group (i.e., having an address in the specified range and being a member of the specified service group) are permitted to respond to the LCPoll. Furthermore, a MAC User in the specified group will only respond to the LCPoll if it has been instructed a priori that it may respond to LCPolls and then only if it has data to transmit.
The responding MAC Users typically transmit a reservation request message rather than a data message in response to the LCPoll. The reservation request message is typically a short duration message which indicates to the headend unit that the MAC User requires bandwidth on the shared channel as well as how much bandwidth is required (which the headend unit provides by sending SPolls to the MAC User). In an exemplary embodiment, the reservation request message is a special NAK message. If exactly one MAC User responds to the LCPoll, then the reservation request message is successfully received by the headend unit, and the responding MAC User is said to have made a reservation. However, if more than one MAC User responds to the LCPoll, then a collision occurs, and the headend unit must resolve the collision by sending LCPolls to successively smaller and smaller subgroups until each MAC User having data to transmit is able to make a reservation.
Upon being group polled, MAC Users on the contention poll list that remain "inactive" (i.e., having no data to transmit) are left on the contention poll list. However, MAC Users on the contention poll list that become "active" (i.e., by making a reservation) are moved onto the select poll list and are instructed (either explicitly or implicitly) by the headend unit to ignore LCPolls.
By moving a MAC User from the select poll list to the contention poll list when the MAC User becomes "inactive," the hybrid contention/polling technique attempts to maintain the select poll list at an optimal level, which aids in the efficient use of select polling. A goal of the hybrid contention/polling technique is to remove MAC Users from the select poll list as early as possible and to react to the needs of the "inactive" MAC Users as quickly as possible. Choosing the predetermined interval equal to one SPoll avoids wasting SPolls on inactive MAC Users, but forces the MAC User to contend anew if it generates data immediately. On the other hand, choosing the predetermined interval greater than one SPoll wastes SPolls on MAC Users that are truly "inactive," but keeps the MAC User "active" in case it generates data again within the predetermined interval. In either case, there are potential inefficiencies if the true state of the MAC User does not match the poll list to which the MAC User is placed. Therefore, a need remains for an improved hybrid contention/polling access method.